package com.kevin.Code.DP;

import javax.print.DocFlavor;

/**
 * @author Vinlee Xiao
 * @Classname MaximalRectangle
 * @Description Leetcode 85. 最大矩形 难度 困难 没啥思路 再做
 * @Date 2021/10/13 22:30
 * @Version 1.0
 */
public class MaximalRectangle {

    /**
     * @param matrix
     * @return
     */
    public int maximalRectangle(char[][] matrix) {

        int row = matrix.length;
        if (row == 0) {
            return 0;
        }
        int col = matrix[0].length;


        //表示i行j列左边连续的1个个数
        int[][] left = new int[row][col];

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {

                if (matrix[i][j] == '0') {
                    continue;
                }

                left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;
            }

        }

        int resutlt = 0;
        for (int i = 0; i < row; i++) {

            for (int j = 0; j < col; j++) {

                if (matrix[i][j] == '0') {
                    continue;
                }
                int width = left[i][j];
                int area = width;

                for (int k = i - 1; k >= 0; k--) {

                    //求最小的宽度
                    width = Math.min(width, left[k][j]);
                    //如果上一行同样列位置的
                    area = Math.max(area, width * (i - k + 1));
                }

                //实时更新最大矩形的位置
                resutlt = Math.max(resutlt, area);
            }

        }

        return resutlt;
    }
}
